Windowed pq-grams for approximate joins of data-centric XML

摘要

在数据集成应用程序中，联接匹配两个数据源共有的元素。由于每个源中元素的表示方式略有不同，因此必须使用近似联接进行匹配。对于XML数据，大多数现有的近似联接策略都基于某种有序的树匹配技术，例如树编辑距离。但是，在以数据为中心的XML中，同级顺序无关紧要，即使两个元素的子元素顺序发生变化，两个元素也应匹配。因此，以数据为中心的XML的近似联接必须利用无序树匹配技术。由于算法不能依赖预定义的同级顺序，因此计算上很困难。在本文中，我们提供了一种基于无序树匹配的近似联接的解决方案。我们解决方案的核心是窗口化的pq-gram，它们是特定形状的小子树。我们开发了一种有效的技术，可通过三步过程生成加窗的pq-gram：对树进行排序，使用虚拟节点扩展已排序的树以及将扩展的树分解为加窗的pq-gram。两棵树之间的开窗pq-gram距离是仅在一棵树分解中的pq-gram的数量。我们证明了我们的距离是伪度量，并通过经验证明了它有效地逼近了无序树编辑距离。使用开窗的pq-gram进行的近似联接可以有效地实现为字符串上的相等联接，从而避免了每对输入树之间距离的昂贵计算。使用合成数据和真实数据进行的实验证实了分析结果，并显示了我们技术的有效性和效率。